

#include "hash.h"

#include <library/string/string.h>

/* Jenkins One-at-a-Time Hash Function */
extern int hash_key (const char *_name)
{
	int k = 0;

	while (*_name != '\0')
	{
		k += *_name;
		k += (k << 10);
		k ^= (k >> 6);

		++_name;
	}
	
	k += (k << 3);
	k ^= (k >> 11);
	k += (k << 15);
	
	return k;
}

#define hash_next(_hash, _k) ((_k + 1) % _hash->Capacity)

extern Hash *hash_request (size _element, size _capacity)
{
	Hash *hash;
	index i;

	hash = (Hash *) block_request (sizeof (Hash));
	hash->Keys = (char **) block_request (sizeof (char *) * _capacity);
	hash->Values = (void **) block_request (sizeof (void *) * _capacity);
	hash->Capacity = _capacity;
	hash->Size = 0;
	hash->ElementSize = _element;
	
	for (i = 0; i < _capacity; ++i)
	{
		hash->Keys [i] = NULL;
		hash->Values [i] = NULL;
	}

	return hash;
}


void hash_release (Hash *_hash)
{
	index i;

	for (i = 0; i < _hash->Capacity; ++i)
	{
		block_release (_hash->Keys [i]);
		block_release (_hash->Values [i]);
	}

	block_release (_hash->Keys);
	block_release (_hash->Values);
	
	block_release (_hash);
}


void *hash_find (Hash *_hash, const char *_name)
{

	return hash_fast (_hash, _name, hash_key (_name));
}


void *hash_fast (Hash *_hash, const char *_name, int _key)
{
	int k;
	int i = 0;
	
	for (k = _key % _hash->Capacity; ; k = hash_next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot; no match found */

			return NULL;
		}

		if (stringequal (_hash->Keys [k], _name))
		{
			/* we found a match! */

			return &_hash->Values [k];
		}

		++i;

		if (i > _hash->Size)
		{
			/* table is full and nothing matches */
			return NULL;
		}
	}
}


void *hash_insert (Hash *_hash, const char *_name)
{
	int k;
	size strsz;
	Hash *temp;

	if (_hash->Size >= _hash->Capacity)
	{
		/* hash is full; we'll grow it */

		temp = hash_request (_hash->ElementSize, _hash->Capacity * 2);

		for (k = 0; k < _hash->Capacity; ++k)
		{
			if (_hash->Keys [k] != NULL)
			{
				rawcopy (hash_insert (temp, _hash->Keys [k]), _hash->Values [k], _hash->ElementSize);

				block_release (_hash->Keys [k]);
			}
		}

		block_release (_hash->Keys);
		block_release (_hash->Values);

		_hash->Keys = temp->Keys;
		_hash->Values = temp->Values;
		_hash->Capacity = temp->Capacity;

		temp->Keys = NULL;
		temp->Values = NULL;
		temp->Capacity = 0;

		hash_release (temp);
	}

	for (k = hash_key (_name) % _hash->Capacity; ; k = hash_next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot ! */
			strsz = stringsize (_name);
			_hash->Keys [k] = (char *) block_request (strsz);
			stringcopy (_hash->Keys [k], _name, strsz);

			_hash->Values [k] = block_request (_hash->ElementSize);

			++_hash->Size;

			return &_hash->Values [k];
		}
	}
}


void hash_remove (Hash *_hash, const char *_name)
{
	int k;
	int i = 0;
	
	for (k = hash (_hash, _name); ; k = hash_next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot; no match found */

			return;
		}

		if (stringequal (_hash->Keys [k], _name))
		{
			/* we found a match! */

			block_release (_hash->Keys [k]);
			_hash->Keys [k] = NULL;

			return;
		}

		++i;

		if (i > _hash->Size)
		{
			/* nothing matches */
			return;
		}
	}
}


